1732E - Location - CodeForces Solution


data structures dp math number theory *2800

Please click on ads to support us..

C++ Code:

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define ll long long
#define vi vector < int >
using namespace std;
const int N = 1 << 17, T = 5e4;
int n, q, tb[N];
unsigned int a[N], b[N], c[N], f[N];
vi vc[N];
bool pr[N];
unsigned int Inv(unsigned int x) {
unsigned int w = 1;
L(t, 0, 31) if((w * x - 1) & ((1LL << (t + 1)) - 1)) w += 1u << t;
return w;
}
unsigned int iv[N];
int main() {
//	freopen("data.in", "r", stdin);
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
L(i, 2, T) if(!vc[i].size()) for(int j = i; j <= T; j += i) vc[j].emplace_back(i);
L(i, 1, T)
if(i & 1) iv[i] = Inv(i), iv[i] *= iv[i];
else iv[i] = iv[i >> 1];
cin >> n >> q ;
L(i, 1, n) cin >> a[i];
L(i, 1, n) cin >> b[i];
L(i, 1, n)
c[i] = (a[i] >> __builtin_ctz(a[i] | b[i])) * iv[__gcd(a[i], b[i])],
a[i] = __builtin_ctz(a[i] | b[i]), tb[i] = __builtin_ctz(b[i]);
while(q--) {
int t, l, r, x;
cin >> t >> l >> r;
if(t == 1) {
cin >> x;
int prd = 1;
f[1] = x;
for(const int &u : vc[x]) {
int xp = 1;
while(x % ((ll) prd * u) == 0) {
for(int blk = 1; blk <= u; blk <<= 1)
memcpy(f + blk * prd + 1, f + 1,
sizeof(unsigned int) * min(u - blk, blk) * prd);
xp *= u, prd *= u;
if(u != 2) for(int i = xp; i <= prd; i += xp) f[i] *= iv[u];
else for(int i = xp; i <= prd; i += xp) f[i] >>= 1;
}
}
L(i, prd + 1, T) f[i] = f[i - prd];
L(i, l, r) c[i] = f[b[i]];
int w = __builtin_ctz(x);
L(i, l, r) a[i] = min(tb[i], w);
} else {
unsigned int ns = -1;
L(i, l, r) ns = min(ns, b[i] * c[i] >> a[i]);
cout << ns << '\n';
}
}
return 0;
}


Comments

Submit
0 Comments
More Questions

1716B - Permutation Chain
987A - Infinity Gauntlet
1676G - White-Black Balanced Subtrees
1716D - Chip Move
1352F - Binary String Reconstruction
1487B - Cat Cycle
1679C - Rooks Defenders
56A - Bar
1694B - Paranoid String
35A - Shell Game
1684A - Digit Minimization
43B - Letter
1017A - The Rank
1698B - Rising Sand
235A - LCM Challenge
1075B - Taxi drivers and Lyft
1562A - The Miracle and the Sleeper
1216A - Prefixes
1490C - Sum of Cubes
868A - Bark to Unlock
873B - Balanced Substring
1401D - Maximum Distributed Tree
1716C - Robot in a Hallway
1688B - Patchouli's Magical Talisman
99A - Help Far Away Kingdom
622B - The Time
1688C - Manipulating History
1169D - Good Triple
1675B - Make It Increasing
588A - Duff and Meat